package wtx.geek;

import com.google.common.collect.Lists;

import java.util.*;
import java.util.Random;

/**
 * You have k lists of sorted integers. Find the smallest range that includes at least one number from each of the k lists.
 *
 * For example,
 * List 1: [4, 10, 15, 24, 26]
 * List 2: [0, 9, 12, 20]
 * List 3: [5, 18, 22, 30]
 *
 * The smallest range here would be [20, 24] as it contains 24 from list 1, 20 from list 2, and 22 from list 3.
 * https://careercup.com/question?id=16759664
 *
 */

public class Solution {

    private static class Pair {
        int value, pos;
        Pair(int l, int r) {
            value = l;
            pos = r;
        }
    }
    public static int[] findSmallestRange(List<List<Integer>> lists) {
        int[] ret = new int[2];
        int k = lists.size();
        int[] indices = new int[k];
        Deque<Pair> sortedTmpList = new LinkedList<>();
        Map<Integer, Integer> incluedList = new HashMap<>();
        boolean notEmpty = true;
        int minRange = Integer.MAX_VALUE;
        while (notEmpty)  {
            while (incluedList.size() < k && notEmpty) {
                Pair smallest = new Pair(Integer.MAX_VALUE, -1);
                notEmpty = false;
                for (int i = 0; i < k; i++) {
                    // find the smallest
                    if (indices[i] < lists.get(i).size()) {
                        int v = lists.get(i).get(indices[i]);
                        if (v < smallest.value) {
                            smallest.pos = i;
                            smallest.value = v;
                        }
                        notEmpty = true;
                    }
                }
                if (notEmpty) {
                    indices[smallest.pos]++;
                    sortedTmpList.add(smallest);
                    incluedList.merge(smallest.pos, 1, (x, y) -> x + y);
                }
            }

            while (sortedTmpList.size() > 0) {
                Pair p = sortedTmpList.pop();
                incluedList.put(p.pos, incluedList.get(p.pos)-1);
                if (incluedList.get(p.pos) == 0 && incluedList.size() == k) {
                   int gap = sortedTmpList.getLast().value - p.value;
                   if (gap < minRange) {
                       minRange = gap;
                       ret[0] = p.value;
                       ret[1] = sortedTmpList.getLast().value;
                   }
                   incluedList.remove(p.pos);
                   break;
                }
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        List<List<Integer>> lists = new ArrayList<>();
        lists.add(Lists.newArrayList(4, 10, 15, 24, 26));
        lists.add(Lists.newArrayList(0, 9, 12, 20));
        lists.add(Lists.newArrayList(5, 18, 22, 30));
        int[] smallestRange = findSmallestRange(lists);
        System.out.println("smalliest range = [" + smallestRange[0] + ", " + smallestRange[1] + "]");
    }


}
